//https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=23452&ru=%2Fpractice%2F9023a0c988684a53960365b889ceaf5e&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路1：利用对称遍历实现；
//思路2：利用队列实现；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
  public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (pRoot == nullptr) return true;
 
        return IsSymmetricalTree(pRoot, pRoot);
 
    }
    bool IsSymmetricalTree(TreeNode* pLeft, TreeNode* pRight) {
        if (pLeft == nullptr && pRight == nullptr) return true;
 
        if (pLeft == nullptr && pRight != nullptr) return false;
 
        if (pRight == nullptr && pLeft != nullptr) return false;
 
        if (pRight->val != pLeft->val) return false;
 
        return IsSymmetricalTree(pLeft->left, pRight->right) &&
               IsSymmetricalTree(pLeft->right, pRight->left);
 
    }
};



class Solution2 {
  public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (pRoot == nullptr) return true;

        std::queue<TreeNode*> t_queue;
        
        t_queue.push(pRoot);
        while(!t_queue.empty()) {
            size_t q_size = t_queue.size();
            std::vector<int> r_vec;
            for(size_t i=0;i<q_size;++i) {
                TreeNode* cur_node = t_queue.front();
                t_queue.pop();
                if (cur_node) {
                    r_vec.push_back(cur_node->val);
                }else {
                    r_vec.push_back(INT_MAX);
                }
                if (cur_node) {
                    t_queue.push(cur_node->left);
                    t_queue.push(cur_node->right);
                }
            }
            size_t l = 0;
            size_t r = r_vec.size()-1;
            for(;l<r;++l, --r){
                if (r_vec[l] != r_vec[r]) return false;
            } 
        }
        return true;
    }
};